package com.sheng.leetcode.year2025.month09.day09;

import org.junit.Test;

/**
 * @author by ls
 * @date 2025/9/16
 * <p>
 * 2327. 知道秘密的人数<p>
 * <p>
 * 在第 1 天，有一个人发现了一个秘密。<p>
 * 给你一个整数 delay ，表示每个人会在发现秘密后的 delay 天之后，每天 给一个新的人 分享 秘密。<p>
 * 同时给你一个整数 forget ，表示每个人在发现秘密 forget 天之后会 忘记 这个秘密。一个人 不能 在忘记秘密那一天及之后的日子里分享秘密。<p>
 * 给你一个整数 n ，请你返回在第 n 天结束时，知道秘密的人数。由于答案可能会很大，请你将结果对 10^9 + 7 取余 后返回。<p>
 * <p>
 * 示例 1：<p>
 * 输入：n = 6, delay = 2, forget = 4<p>
 * 输出：5<p>
 * 解释：<p>
 * 第 1 天：假设第一个人叫 A 。（一个人知道秘密）<p>
 * 第 2 天：A 是唯一一个知道秘密的人。（一个人知道秘密）<p>
 * 第 3 天：A 把秘密分享给 B 。（两个人知道秘密）<p>
 * 第 4 天：A 把秘密分享给一个新的人 C 。（三个人知道秘密）<p>
 * 第 5 天：A 忘记了秘密，B 把秘密分享给一个新的人 D 。（三个人知道秘密）<p>
 * 第 6 天：B 把秘密分享给 E，C 把秘密分享给 F 。（五个人知道秘密）<p>
 * <p>
 * 示例 2：<p>
 * 输入：n = 4, delay = 1, forget = 3<p>
 * 输出：6<p>
 * 解释：<p>
 * 第 1 天：第一个知道秘密的人为 A 。（一个人知道秘密）<p>
 * 第 2 天：A 把秘密分享给 B 。（两个人知道秘密）<p>
 * 第 3 天：A 和 B 把秘密分享给 2 个新的人 C 和 D 。（四个人知道秘密）<p>
 * 第 4 天：A 忘记了秘密，B、C、D 分别分享给 3 个新的人。（六个人知道秘密）<p>
 * <p>
 * 提示：<p>
 * 2 <= n <= 1000<p>
 * 1 <= delay < forget <= n<p>
 */
public class LeetCode2327 {

    @Test
    public void test() {
//        int n = 6, delay = 2, forget = 4;
        int n = 4, delay = 1, forget = 3;
        System.out.println(new Solution().peopleAwareOfSecret(n, delay, forget));
    }
}

class Solution {

    private static final int MOD = 1000000007;

    public int peopleAwareOfSecret(int n, int delay, int forget) {
        // 假如都在规定的时间内，那么 A 从发现秘密开始，会依次分享给 forget - delay 个人
        // konwn[i] 表示恰好在第 i 天得知秘密的人数
        int[] konwn = new int[n + 1];
        konwn[1] = 1;
        long ans = 0;
        for (int i = 1; i <= n; i++) {
            // 统计在第 n 天没有忘记秘密的人数
            // 这要求 i + forget - 1 >= n，解得 i >= n - forget + 1
            if (i >= n - forget + 1) {
                ans += konwn[i];
            }
            // 恰好在第 i 天得知秘密的人，会在第 [i + delay, i + forget - 1] 天的时候，分享秘密
            for (int j = i + delay; j <= Math.min(n, i + forget - 1); j++) {
                konwn[j] = (konwn[j] + konwn[i]) % MOD;
            }
        }
        return (int) (ans % MOD);
    }
}
